package String;

import javax.swing.text.html.parser.Entity;
import java.util.*;

public class _767_ReorganizeString {

    public String reorganizeString(String S) {
        int[] alphabet = new int[26];
        for (int i = 0; i < S.length(); i++) {
            alphabet[S.charAt(i)-'a']+=100;
        }
        for(int i=0;i<26;i++) {
            alphabet[i]+=i;
        }
        char[] result = new char[S.length()];
        int start = 1;
        Arrays.sort(alphabet);
        for (int i = 0; i < alphabet.length; i++) {
            int count = alphabet[i]/100;
            char c = (char)(alphabet[i]% 100 + 'a');
            if (count > (S.length() + 1) / 2) {
                return "";
            }
            while (count > 0) {
                if (start > S.length()-1) {
                    start = 0;
                }
/*                System.out.println("start:"+start);
                System.out.println((char)('a'+i));*/
                result[start] =c;
                start += 2;
                count--;
            }
        }
        return new String(result);
    }
    //solution 1:huse hashMap and count,too complecated
    /*public String reorganizeString(String S) {
        Map<Character, Integer> map = new HashMap<>();
        List<Character> letterList = new ArrayList<>();
        char maxLetter = 'a';
        int max = 0;
        int length = S.length();
        int count = length;
        for (char c : S.toCharArray()) {
            if (map.containsKey(c)) {
                int tempCount = map.get(c)+1;
                if (tempCount > max) {
                    max = tempCount;
                    maxLetter = c;
                }
                map.put(c, tempCount);
            } else {
                if (max == 0) {
                    maxLetter = c;
                    max = 1;
                }
                letterList.add(c);
                map.put(c, 1);
            }
        }
        //sub-situation discuss with odd and even length
        if (length % 2 == 0) {
            if (max > length / 2) {
                return "";
            }
        } else {
            if (max > length / 2 + 1) {
                   return "";
            }
        }
        //rearange the string
        String result = "";
        int pos = 0;
        while (max >= 0) {
            if (result.length() % 2 == 0) {
                result+=maxLetter;
                count--;
                max--;
                map.put(maxLetter, max);
            } else {
                for (int i = 0; i <letterList.size(); i++) {
                    if (i >= pos) {
                        if (map.get(letterList.get(i)) > 0) {
                            result+=letterList.get(i);
                            count--;
                            map.put(letterList.get(i), map.get(letterList.get(i)) - 1);
                        }
                        pos++;
                    } else {
                        pos++;
                    }
                    if (pos == letterList.size()-1) {
                        pos = 0;
                    }
                }
            }
        }
        pos = 0;
        while (count > 0) {
            for (int i = 0; i <letterList.size(); i++) {
                if (i >= pos) {
                    if (map.get(letterList.get(i)) > 0) {
                        result+=letterList.get(i);
                        count--;
                        map.put(letterList.get(i), map.get(letterList.get(i)) - 1);
                    }
                    pos++;
                } else {
                    pos++;
                }
                if (pos == letterList.size()-1) {
                    pos = 0;
                }
            }
        }
        return result;
    }*/
}
